The present invention relates to decoding, and, more particularly, to a decoding method and apparatus for a Huffman code.
Huffman codes are commonly used in various applications such as, for example, in compression/decompression algorithms for digital, audio or video signals. In a Huffman code, each item of source data (symbol) is coded by a variable number of bits which is inversely proportional to a statistical frequency of use of the source data. The coded data is generally supplied by a continuous stream of bits without any separator element (control element) so as to increase the level of compression.
The source data is obtained from the corresponding coded data using special decoding tables. In particular, a look-up table (LUT) is used in which each row contains a flag indicating whether an index for access to the row represents an item of coded data. If this is the case, the row contains a field which specifies the associated source data. The bits of the coded data received in sequence are used to form the index of the decoding table, until a row, the flag of which indicates an item of coded data, is reached. The corresponding source data is obtained from this row.
If Max indicates the maximum number of bits of the coded data, the decoding table must therefore have a number of rows substantially equal to 2Max. This involves an extremely large amount of memory, in particular, in the case where there are several alternative decoding tables, which are selected according to the various statistical distribution of the source data.
Another known decoding method groups together the possible values of the coded data in clusters, each including a number of bits ranging between two consecutive multiples of a predefined value. Each cluster has associated with it, for each value of the maximum number of bits added to the preceding cluster, a row of the decoding table which contains a coded data flag. If the flag indicates an item of coded data, the row contains two fields which specify the associated source data and its length. In the opposite case, the two fields specify an address of the next cluster and its maximum length.
The maximum number of bits of the first cluster is used to access a row of the decoding table. The decoding method repeatsxe2x80x94until it reaches a row, the flag of which indicates an item of coded dataxe2x80x94the steps for selecting the bits of the next cluster (the number of which is obtained from the current row) and accessing the row corresponding to their value (using the address obtained from the current row). The source data and its actual length are obtained from the fields of the row thus obtained. In this way, it is possible to reduce substantially the amount of memory occupied by the decoding table.
A drawback of the known approach described above is that the decoding method requires a lot of feedback cycles. This makes the decoding method somewhat complex and slow. Moreover, the amount of memory occupied by the decoding table is, in any case, not insignificant.
An object of the present invention is to overcome the abovementioned drawbacks. This and other objects, features and advantages are provided by a decoding method for a Huffman code, comprising the steps of receiving a continuous stream of coded data each including a variable number of bits at least equal to a minimum number, and obtaining from each item of coded data a corresponding item of source data. A decoding memory structure is provided which comprises, for each value of an initial group of bits comprising a number not greater than the minimum number and for each value of each further bit, a record formed by a flag having an end-of-decoding value or a not end-of-decoding value and a field indicating the source data or the records associated with the values of an immediately following bit depending on whether the flag has, respectively, the end value or the not end value.
The method further includes accessing the record corresponding to the value of the initial group, and repeatingxe2x80x94until a record having the flag with the end value is reachedxe2x80x94the step of accessing the record corresponding to the value of the immediately following bit using the field of the current record. The source data is obtained from the field of the current record.
Moreover, a corresponding processor program, program product and processing system are provided for decoding a Huffman code.